import unittest
import copy

class Comparable(object):
    compare_counter = 0
    debug = False

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Comparable.compare_counter += 1
        if Comparable.debug:
            print self.value, other.value
        return self.value < other.value

    def __ge__(self, other):
        return not __lt__(self, other)

    def __eq__(self, other):
        return self.value == other.value

    def __ne__(self, other):
        return not __eq__(self, other)

    def __repr__(self):
        return str(self.value)

output = [Comparable(1), Comparable(2), Comparable(3), Comparable(4)]

class TestSort(unittest.TestCase):
    
    def testInsertionSort(self):
        from sort import insertion_sort

        # Test boundary condition
        self.assertEqual(insertion_sort([]), [])
        self.assertEqual(insertion_sort([1]), [1])

        # Best condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        self.assertEqual(insertion_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 3)

        # Worst condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        self.assertEqual(insertion_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

    def testMergeSort(self):
        from sort import merge_sort

        # Test boundary condition
        self.assertEqual(merge_sort([]), [])
        self.assertEqual(merge_sort([1]), [1])

        # Best condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        self.assertEqual(merge_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 4)

        # Worst condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        self.assertEqual(merge_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 4)

    def testBubbleSort(self):
        from sort import bubble_sort

        # Test boundary condition
        self.assertEqual(bubble_sort([]), [])
        self.assertEqual(bubble_sort([1]), [1])

        # Best condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        self.assertEqual(bubble_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

        # Worst condition
        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        self.assertEqual(bubble_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

    def testHeapSort(self):
        from sort import heap_sort
        from heap import max_heap
        self.assertRaises(AssertionError, max_heap.parent, -1)
        self.assertRaises(AssertionError, max_heap.parent, 0)
        self.assertEqual(max_heap.parent(1), 0)
        self.assertEqual(max_heap.parent(2), 0)
        self.assertEqual(max_heap.left_child(0), 1)
        self.assertEqual(max_heap.right_child(0), 2)

        Comparable.compare_counter = 0
        input = copy.copy(output)
        h = max_heap(input)
        self.assertEqual(h.first_leaf(), 2)
        self.assertEqual(h.array, [Comparable(4), Comparable(2), Comparable(3), Comparable(1)])
        self.assertEqual(Comparable.compare_counter, 4)

        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        h = max_heap(input)
        self.assertEqual(h.array, input)
        self.assertEqual(Comparable.compare_counter, 3)
        
        Comparable.compare_counter = 0
        input = copy.copy(output)
        self.assertEqual(heap_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 7)

        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        self.assertEqual(heap_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

    def testQuickSort(self):
        from sort import quick_sort

        Comparable.compare_counter = 0
        input = copy.copy(output)
        self.assertEqual(quick_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

        Comparable.compare_counter = 0
        input = copy.copy(output)
        input.reverse()
        self.assertEqual(quick_sort(input), output)
        self.assertEqual(Comparable.compare_counter, 6)

if __name__ == '__main__':
    unittest.main()
